package leetcode_周赛._2021._202105._20210523;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/23 11:06
 * 准时到达的列车最小时速
 * 算法：二分查找
 * 时速是最小正整数
 * 由于每趟的最优时间是一小时，坐车时间加上等待时间的最优时间是一小时
 * 前 dist.length - 1 的距离要保持在一小时之内，而最后一个距离是 (hour - (dist.length - 1) ) / (dist[dist.length - 1])
 */
public class _5764 {
    public static void main(String[] args) {
        System.out.println(new _5764().minSpeedOnTime(new int[]{1, 3, 2}, 6));
    }

    public int minSpeedOnTime(int[] dist, double hour) {
        if (hour - (double) (dist.length - 1) < 0) return -1;
        double right = 0;
        for (int i = 0; i < dist.length - 1; i++) right = Math.max(right, dist[i]);
        right = Math.max(right, Math.ceil(dist[dist.length - 1] / (hour - dist.length + 1)));
        double left = 1;
        while (left < right) {
            double mid = (left + right) / 2;
            double need = 0;
            for (int i = 0; i < dist.length - 1; i++) {
                if (dist[i] % mid == 0) need += dist[i] / mid;
                else need += dist[i] / mid + 1;
            }
            need += dist[dist.length - 1] / mid;
            if (need <= hour) right = mid;
            else left = mid + 1;
        }
        if (left > 10000000) left -= 1;
        return (int)left;
    }

}
